# class Solution(object):
#     def minReverseOperations(self, n, p, banned, k):
#         a_ready = {p}
#         banned = set(banned)
#         now = {p}
#         dist = 0
#         ans = [-1] * n
#         while now:
#             next_st = set()
#             for node in now:
#                 ans[node] = dist
#                 for start in range(max(0, node - k + 1), node + 1):
#                     end = start + k - 1
#                     if end >= n:
#                         break
#                     next_p = start + end - node
#                     if next_p not in a_ready:
#                         a_ready.add(next_p)
#                         if next_p not in banned:
#                             next_st.add(next_p)
#             now = next_st
#             dist += 1
#         return ans
import sortedcontainers
class Solution(object):
    def minReverseOperations(self, n, p, banned, k):
        banned = set(banned)
        now = {p}
        dist = 0
        ans = [-1] * n
        wait_list = [i for i in range(n)]
        ji_wait_list = wait_list[1::2]
        ou_wait_list = wait_list[::2]
        ji_wait_list = sortedcontainers.SortedList(ji_wait_list)
        ou_wait_list = sortedcontainers.SortedList(ou_wait_list)
        if p % 2 == 1:
            ji_wait_list.remove(p)
        else:
            ou_wait_list.remove(p)
        wait_list = sortedcontainers.SortedList(wait_list)
        wait_list.remove(p)
        while now:
            next_st = set()
            for node in now:
                ans[node] = dist
                start_min = max(0, node - k + 1)
                start_max = min(node, n - k)
                next_p_min = 2 * start_min + k - 1 - node
                next_p_max = 2 * start_max + k - 1 - node
                if next_p_min <= next_p_max:
                    if k % 2 == 0:
                        if node % 2 == 0:
                            left_index = ji_wait_list.bisect_left(next_p_min)
                            right_index = ji_wait_list.bisect_right(next_p_max)
                            count = right_index - left_index
                            while count > 0:
                                next_p = ji_wait_list.pop(left_index) 
                                count -= 1
                                if next_p not in banned:
                                    next_st.add(next_p)
                        else:
                            left_index = ou_wait_list.bisect_left(next_p_min)
                            right_index = ou_wait_list.bisect_right(next_p_max)
                            count = right_index - left_index
                            while count > 0:
                                next_p = ou_wait_list.pop(left_index) 
                                count -= 1
                                if next_p not in banned:
                                    next_st.add(next_p)
                    else:
                        if node % 2 == 1:
                            left_index = ji_wait_list.bisect_left(next_p_min)
                            right_index = ji_wait_list.bisect_right(next_p_max)
                            count = right_index - left_index
                            while count > 0:
                                next_p = ji_wait_list.pop(left_index) 
                                count -= 1
                                if next_p not in banned:
                                    next_st.add(next_p)
                        else:
                            left_index = ou_wait_list.bisect_left(next_p_min)
                            right_index = ou_wait_list.bisect_right(next_p_max)
                            count = right_index - left_index
                            while count > 0:
                                next_p = ou_wait_list.pop(left_index) 
                                count -= 1
                                if next_p not in banned:
                                    next_st.add(next_p)

            now = next_st
            dist += 1
        return ans

data = Solution()
n = 4
p = 0
banned = []
k = 4
print(data.minReverseOperations(n, p, banned, k))
n = 4
p = 2
banned = []
k = 4
print(data.minReverseOperations(n, p, banned, k))
n = 5
p = 0
banned = []
k = 2
print(data.minReverseOperations(n, p, banned, k))